package com.hanxiaozhang.recursion.violentrecursion;

/**
 * 〈一句话功能简述〉<br>
 * 〈打印n层汉诺塔从最左边移动到最右边的全部过程〉
 *
 * @author hanxinghua
 * @create 2021/10/6
 * @since 1.0.0
 */
public class Hanoi {


    public static void main(String[] args) {
        int n = 3;
        hanoi1(n);
        System.out.println("============");
        hanoi2(n);
        System.out.println("============");
    }

    /**
     * 实现1
     *
     * @param n
     */
    public static void hanoi1(int n) {
        leftToRight(n);
    }


    /**
     * 请把1 ~ N层圆盘，从左 -> 右
     *
     * @param n
     */
    public static void leftToRight(int n) {
        // 如果剩下一个，就代表移动完成
        if (n == 1) {
            System.out.println("Move 1 from left to right");
            return;
        }
        // (大步骤，递归) 将 1 ~ N-1 层圆盘，从左 -> 中
        leftToMid(n - 1);
        // 将 N 层圆盘，从左 -> 右
        System.out.println("Move " + n + " from left to right");
        // (大步骤，递归) 将 1 ~ N-1 层圆盘，从中 -> 右
        midToRight(n - 1);
    }

    /**
     * 请把1 ~ N层圆盘，从左 -> 中间
     *
     * @param n
     */
    public static void leftToMid(int n) {
        // 如果剩下一个，就代表移动完成
        if (n == 1) {
            System.out.println("Move 1 from left to mid");
            return;
        }
        // (大步骤，递归) 将 1 ~ N-1 层圆盘，从左 -> 右
        leftToRight(n - 1);
        // 将 N 层圆盘，从左 -> 中
        System.out.println("Move " + n + " from left to mid");
        // (大步骤，递归) 将 1 ~ N-1 层圆盘，从右 -> 中
        rightToMid(n - 1);
    }

    /**
     * 请把1 ~ N层圆盘，从右 -> 中
     *
     * @param n
     */
    public static void rightToMid(int n) {
        if (n == 1) {
            System.out.println("Move 1 from right to mid");
            return;
        }
        rightToLeft(n - 1);
        System.out.println("Move " + n + " from right to mid");
        leftToMid(n - 1);
    }

    /**
     * 请把1 ~ N层圆盘，从中 -> 右
     *
     * @param n
     */
    public static void midToRight(int n) {
        if (n == 1) {
            System.out.println("Move 1 from mid to right");
            return;
        }
        midToLeft(n - 1);
        System.out.println("Move " + n + " from mid to right");
        leftToRight(n - 1);
    }

    /**
     * 请把1 ~ N层圆盘，从中 -> 左
     *
     * @param n
     */
    public static void midToLeft(int n) {
        if (n == 1) {
            System.out.println("Move 1 from mid to left");
            return;
        }
        midToRight(n - 1);
        System.out.println("Move " + n + " from mid to left");
        rightToLeft(n - 1);
    }

    /**
     * 请把1 ~ N层圆盘，从右 -> 左
     *
     * @param n
     */
    public static void rightToLeft(int n) {
        if (n == 1) {
            System.out.println("Move 1 from right to left");
            return;
        }
        rightToMid(n - 1);
        System.out.println("Move " + n + " from right to left");
        midToLeft(n - 1);
    }


    /**
     * 算法2
     *
     *
     * @param n
     */
    public static void hanoi2(int n) {
        if (n > 0) {
            func(n, "left", "right", "mid");
        }
    }


    /**
     * 1~N 圆盘 目标是from -> to， other是另外一个
     *
     * @param N
     * @param from
     * @param to
     * @param other
     */
    public static void func(int N, String from, String to, String other) {
        // 如果剩下一个，就代表移动完成
        if (N == 1) {
            System.out.println("Move 1 from " + from + " to " + to);
        } else {
            func(N - 1, from, other, to);
            System.out.println("Move " + N + " from " + from + " to " + to);
            func(N - 1, other, to, from);
        }
    }

}
